 //25.K个一组翻转链表
 //https://leetcode.cn/problems/reverse-nodes-in-k-group
class Solution {
    void reverse_list(ListNode* head)
    {
        ListNode* start = head, * tail = head->next;
        ListNode* nxt = tail->next;
        while (tail)
        {
            tail->next = start;
            start = tail;
            tail = nxt;
            if(nxt) nxt = nxt->next;
        }
        head->next = nullptr;

    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k <= 1) return head;
        int cnt = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            ++cnt;
        }
        cnt /= k; //知道有几组需要逆置
        cur = head;
        ListNode* prev = nullptr;
        for (int i = 0; i < cnt; ++i)
        {
            //找到需要逆置的链表尾节点
            ListNode* start = cur;
            ListNode* tail = cur;
            for (int i = k; i > 1; --i) tail = tail->next;
            cur = tail->next; //下一个链表的起始位置
            tail->next = nullptr;
            if (prev) prev->next = tail; //上一段链表链接下一段
            reverse_list(start);
            prev = start;
            if (i == 0) head = tail;
        }
        if (cur) prev->next = cur;
        return head;
    }
};